package LeetCode;

import java.util.*;

public class LC_127_WordLadder {
    public static void main(String[] args) {

    }


    class Solution {

        public int ladderLength(String beginWord, String endWord, List<String> wordList) {
            if (beginWord == null || endWord == null || beginWord.length() == 0 || endWord.length() == 0 || beginWord.length() != endWord.length())
                return 0;
            Set<String> set = new HashSet<>(wordList);
            if (set.contains(beginWord)) set.remove(beginWord);
            Queue<String> wordQueue = new LinkedList<>();
            int level = 1;
            int curnum = 1;
            int nextnum = 0;
            wordQueue.add(beginWord);
            while (!wordQueue.isEmpty()) {
                String word = wordQueue.poll();
                curnum--;
                for (int i = 0; i < word.length(); i++) {
                    char[] wordunit = word.toCharArray();
                    for (char j = 'a'; j <= 'z'; j++) {
                        wordunit[i] = j;
                        String temp = new String(wordunit);
                        if (set.contains(temp)) {
                            if (temp.equals(endWord)) return level + 1;
                            nextnum++;
                            wordQueue.add(temp);
                            set.remove(temp);
                        }
                    }
                }
                if (curnum == 0) {
                    curnum = nextnum;
                    nextnum = 0;
                    level++;
                }
            }
            return 0;
        }

    }
}
